#define BOOST_TEST_MODULE "Test for minimum circumscribed circle"

#include <boost/test/unit_test.hpp>
#include <boost/test/test_tools.hpp>
#include <iostream>
#include <time.h>
#include <vector>

#include "../predicates.h"

circle minimum_covering_circle(std::vector<point>& vertices, size_t k1, size_t k2)
{
    circle c(vertices[k1], vertices[k2]);

    for (size_t i = 0; i < k2; ++i)
    {
        if (!point_in_circle(vertices[i], c))
        {
            c = circle(vertices[i], vertices[k1], vertices[k2]);
        }
    }

    return c;
}

circle minimum_covering_circle(std::vector<point>& vertices, size_t k1)
{
    circle c(vertices[0], vertices[k1]);

    for (size_t i = 1; i < k1; ++i)
    {
        if (!point_in_circle(vertices[i], c))
        {
            c = minimum_covering_circle(vertices, k1, i);
        }
    }

    return c;
}

circle minimum_covering_circle(std::vector<point>& vertices)
{
    if (vertices.size() == 1)
    {
        return circle(vertices[0]);
    }

    std::random_shuffle(vertices.begin(), vertices.end());

    circle c(vertices[0], vertices[1]);

    for (size_t i = 2; i < vertices.size(); ++i)
    {
        if (!point_in_circle(vertices[i], c))
        {
            c = minimum_covering_circle(vertices, i);
        }
    }

    std::sort(c.boundaries.begin(), c.boundaries.end());

    return c;
}

/*int main()
{
    size_t n;
    std::cin >> n;

    std::set<point> vertices;

    point tmp;

    for (size_t i = 0; i < n; i++)
    {
        std::cin >> tmp;
        vertices.push_back(tmp);
    }

    circle c = minimum_covering_circle_wrapper(vertices);

    std::cout << c.center.x << " " << c.center.y << " " << c.radius;
}*/

BOOST_AUTO_TEST_CASE(usual_cases)
{
    std::vector<point> vertices;
    vertices.push_back(point(3, 1));
    vertices.push_back(point(0.8, -0.2));
    vertices.push_back(point(2, 2));
    vertices.push_back(point(-0.5, 1));
    vertices.push_back(point(1, 3));

    circle c = minimum_covering_circle(vertices);

    std::vector<point> result;
    result.push_back(point(-0.5, 1));
    result.push_back(point(1, 3));
    result.push_back(point(3, 1));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());

    /***/

    vertices.push_back(point(2, -0.5));

    c = minimum_covering_circle(vertices);

    result.erase(result.begin(), result.end());
    result.push_back(point(-0.5, 1));
    result.push_back(point(1, 3));
    result.push_back(point(2, -0.5));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());

    /***/

    vertices.erase(vertices.begin(), vertices.end());

    vertices.push_back(point(1, 1));
    vertices.push_back(point(1, 5));
    vertices.push_back(point(-1, 3));
    vertices.push_back(point(3, 3));

    c = minimum_covering_circle(vertices);

    result.erase(result.begin(), result.end());
    result.push_back(point(-1, 3));
    result.push_back(point(1, 1));
    result.push_back(point(1, 5));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());

    /***/

    vertices.push_back(point(2, 2));
    vertices.push_back(point(1, 3));

    c = minimum_covering_circle(vertices);

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());
}

BOOST_AUTO_TEST_CASE(degenerate_cases)
{
    std::vector<point> vertices;
    vertices.push_back(point(2, 2));

    circle c = minimum_covering_circle(vertices);

    std::vector<point> result;
    result.push_back(point(2, 2));
    result.push_back(point(2, 2));
    result.push_back(point(2, 2));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());

    /***/

    vertices.push_back(point(-999998, 2));
    vertices.push_back(point(1000002, 2));

    c = minimum_covering_circle(vertices);

    result.erase(result.begin(), result.end());
    result.push_back(point(-999998, 2));
    result.push_back(point(2, -999998));
    result.push_back(point(1000002, 2));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());

    /***/

    vertices.erase(vertices.begin(), vertices.end());
    vertices.push_back(point(0, 0));
    vertices.push_back(point(100, 100));
    vertices.push_back(point(0, 100));
    vertices.push_back(point(0, 0));

    c = minimum_covering_circle(vertices);

    result.erase(result.begin(), result.end());
    result.push_back(point(0, 0));
    result.push_back(point(0, 100));
    result.push_back(point(100, 100));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());

    /***/

    vertices.erase(vertices.begin(), vertices.end());
    vertices.push_back(point(0, 0));
    vertices.push_back(point(1, 0));
    vertices.push_back(point(2, 0));
    vertices.push_back(point(3, 0));
    vertices.push_back(point(4, 0));
    vertices.push_back(point(5, 0));
    vertices.push_back(point(6, 0));
    vertices.push_back(point(7, 0));

    c = minimum_covering_circle(vertices);

    vertices.push_back(point(0, 0));
    vertices.push_back(point(7, 0));

    BOOST_CHECK_EQUAL_COLLECTIONS(c.boundaries.begin(), c.boundaries.end(), result.begin(), result.end());
}